package com.ting.test.algorithms.并查集;

public class UnionFindByArr {
    int[] parent;//int [i]=i 表示元素i的父元素是i
    int[] help = new int[]{};//辅助
    int[] size = new int[]{};//int [i]=k 表示元素i所代表的的集合的大小为k
    int sets = 0;//表示集合数

    public UnionFindByArr(int n) {
        this.parent = new int[n];
        this.help = new int[n];
        this.size = new int[n];
        this.sets = n;//初始化时 一个元素就是一个集合
        for (int i = 0; i < n; i++) {//注意 初始化时 一定要根据题意初始化 不是所有的位置的元素都是有效的
            parent[i] = i;//初始化时，每个元素的父元素是他本身
            size[i] = 1;//每个集合的大小为1，只有他自己一个元素
        }
    }


    /**
     * 专门针对岛问题
     * @param arr
     */
    public UnionFindByArr(int[][] arr) {
        int col=arr[0].length;
        int row=arr.length;
        this.parent = new int[col*row];
        this.help = new int[col*row];
        this.size = new int[col*row];
        this.sets =0;//初始化时 一个元素就是一个集合
        for (int i = 0; i < row; i++) {//注意 初始化时 一定要根据题意初始化 不是所有的位置的元素都是有效的
            for(int j=0;j<col;j++){
                if(arr[i][j]==1){
                    parent[getIndex(arr,i,j)] = getIndex(arr,i,j);//初始化时，每个元素的父元素是他本身
                    size[getIndex(arr,i,j)] = 1;//每个集合的大小为1，只有他自己一个元素
                    sets++;
                }
            }
        }
    }

    /**
     * 如果getTopFather()方法的复杂度为O(1)
     * 则isSameSet()方法的复杂度为O(1)
     *
     * @param x
     * @param y
     * @return
     */
    public boolean isSameSet(int x, int y) {
        return getTopFather(x) == getTopFather(y);
    }

    /**
     * * 如果getTopFather()方法的复杂度为O(1)
     * * 则union()方法的复杂度为O(1)
     *
     * @param x
     * @param y
     */
    public void union(int x, int y) {
        int nx = getTopFather(x);
        int ny = getTopFather(y);
        if(nx==ny){
            return;
        }
        int nxSize = size[nx];
        int nySize = size[ny];

        Boolean nxSmall = nxSize <= nySize ? true : false;
        if (nxSmall) {
            parent[nx] = ny;//将nx的父元素指针指向ny,表示将nx代表的集合挂载ny代表的集合上
            size[ny] = nxSize + nySize;
            size[nx] = -1;//-1表示nx不是代表元素
        }else {
            parent[ny] = nx;//将nx的父元素指针指向ny,表示将nx代表的集合挂载ny代表的集合上
            size[nx] = nxSize + nySize;
            size[ny] = -1;//-1表示nx不是代表元素
        }
        sets--;

    }

    /**
     * 岛问题专用
     * @param arr
     * @param i
     * @param j
     * @return
     */
    public   int getIndex(int[][] arr, int i, int j) {
        return i * arr[0].length + j;
    }

    /**
     * 在寻找当前集合的代表元素时，将沿途查找到的元素的父节点全部设置为代表元素
     * 注意，每次只将涉及到的元素进行调整，其余元素不变
     * 如此则整个集合的高度会越来越低
     * 那么当getTopFather()方法调用十分频繁时(超过O(n)次)，getTopFather()方法的复杂度接近O(1)
     *
     * @param nx
     * @return
     */
    private int getTopFather(int nx) {
        int i = 0;
        while (parent[nx] != nx) {
            help[i++] = nx;
            nx = parent[nx];
        }
        while (i > 0) {
            help[i] = nx;
            i--;
        }
        return nx;
    }

    class Node<V> {
        V v;

        public V getV() {
            return v;
        }

        public void setV(V v) {
            this.v = v;
        }
    }

    public int getSets() {
        return sets;
    }
}
